package huawei;
/*
* @Author: wanghongfucoder
* @Date:   2017-06-27 13:26:53
* @Last Modified by:   wanghongfucoder
* @Last Modified time: 2017-06-27 14:34:27
*/

import java.util.Arrays;
public class Lis {
	public static void main(String[] args) {
		int[] arr={2,1,5,3,6,4,8,9,7};
		int len=lis(arr);
		System.out.println(len);
	}
	public static  int lis(int[] nums){
		int max = 1;  
        int[] dp = new int[nums.length];  
        for (int i = 0; i < nums.length; i++) {  
            dp[i] = 1;  
            for (int j = 0; j < i; j++) {  
                if (nums[j]<nums[i]) {  
                    dp[i] = Math.max(dp[i], dp[j]+1);  
                    max = Math.max(dp[i], max);  
                }  
            }  
        }  
        return max;  
	}	
}
